1. Field of the Invention
The present invention relates to digital communication systems. More particularly, the invention relates to decision decoding of received digital information for use in subsequent decoding processes as well as to weighting selected received coded data based on its estimated reliability prior to decoding.
2. Background of the Related Art
The process of transmitting digital information may in one sense be thought of as a four-step process as shown in FIG. 1. First, an incoming data stream of electrical digital signals x(t) is coded by a coder 10 to produce coded information C(x(t)) that is provided to a transmitter 20 which transmits the coded information C(x(t)) over a communication medium 30. The coder 10 processes the data stream x(t) so that the coded information C(x(t)) is robust to errors; that is, errors in the coded information C(x(t)) can be detected and corrected. This is necessary because, as will be seen, the transmission process introduces a noise component into the transmitted signal which would corrupt the signal and render it useless were it impossible to be removed.
In an exemplary case, the incoming data x(t) is digitized audio such as voice or music from a known source; the coding unit 10 applies a coding transformation to the incoming data x(t) to produce the coded information C(x(t)); and the transmitter 20 modulates a radio-frequency signal with the coded data C(x(t)) to send it as a radio-frequency signal through the atmosphere which serves as the communication medium 30.
In traversing the communication medium 30, the transmitted information C(x(t)) acquires a noise component n(t), and the resultant signal C(x(t))+n(t) received by a receiver 40 is decoded by a decoding unit 50 to recover the original data stream. Through the use of error-checking and correction properties of the coding algorithm employed by the decoder 50, the noise component n(t) can be detected and removed from the received signal C(x(t))+n(t), after which the signal C(x(t)) is processed in the decoder 50 using an algorithm complementary to the one used in the coder 10 to obtain the original data stream x(t).
The term “noise” as used herein is intended to include any source of signal degradation, including but not limited to thermal noise, circuit noise and interference. For single carrier (equalized) systems, the preferred scheme includes identifying those bits in particular bit patterns that are most likely to be received in error, and weighting/puncturing those bits.
In the above example, the receiver 40 demodulates the received radio frequency signal to produce the received coded information C(x(t))+n(t). The received coded information is error-checked and decoded by the decoding unit 50 to produce the outgoing digital data stream which might then be converted to an analog signal to be amplified for driving a speaker.
It is common in systems such as the one described above for the coder 10 to code C(x(t)) using a convolutional coding system. In contrast to a block code where a block of bits is coded according to a rule defined by the code without regard to previous inputs to the coder, a convolutional code additionally makes use of previous bits it processed in the coding process; thus, the coder 10 is a type of finite state machine.
An example of a convolutional coder of a type which might be used in the coder 10 is shown in FIG. 2A. As is evident from the coder block diagram, coding in this unit depends not only on the state of the current input bit xn but also on the state of the two previous input bits held in the two latches D. Consequently, the coder is a four-state machine as shown by its state diagram in FIG. 2B. From the state diagram it is relatively straightforward to derive the coder's trellis diagram as shown in FIG. 2C. Here, the branch to a particular state corresponding to a zero input is represented by a solid arrow, and the branch to a particular state corresponding to a one input is represented by a dotted arrow.
With the trellis diagram of FIG. 2C, the coding process will be readily apparent to those skilled in the art. Applying an input vector of, e.g., X=(1 1 0 1 0 1 1) produces outputs from the coder of FIG. 2A as shown in TABLE I (assuming the coder starts from an all-zero state).
TABLE IInputInternalOutputxIState D1D2y1y2100111100101101101000101010100110010110100111Thus, for the coder of FIG. 2A, C(X)=(1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1).
If the communication medium 30 were error-free and the receiver 40 were assured of providing C(X) to the decoder 50, it could recover the original data stream simply by applying C(X) to the trellis network of the coder state machine and track the path therethrough which generated the sequence C(X). For example, C(X) (1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1) would be generated by the path shown in FIG. 3, where states occupied by the coder are shaded and branches taken by the coder are in bold, with the corresponding coder output C(X) given above each stage. From this, the original input sequence X=(1 1 0 1 0 1 1) can be obtained.
The above discussion and those hereinafter assume that the coder 10 and decoder 50 operate according to the same coding algorithm; that is, they both base their processing on the same coder circuit, state machine and the like; thus, dimensions of the trellis network necessary to accurately represent the coding algorithm are known to the decoder, the number of stages necessary in the trellis network is known, etc. Further, it is assumed that the coder state machine begins in an all-zero state, and that the input stream X is padded with a sufficient number of zeroes to return it to such a state at the conclusion of the coding/decoding process.
Assume now that the signal received and processed by the receiver 40 has a non-zero noise component n(t), i.e., C′(X=C(X)+n(t). This might result in the decoding unit 50 receiving C′(X)=(1 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 1 1), with the sixth and eleventh bits being errors due to n(t). In this case, the original input sequence cannot be found simply by applying C′(X) to the trellis of FIG. 2C. A typical error-correction algorithm used in this situation is the Viterbi error correction algorithm described as follows.
1. Given the trellis network, associate a metric with each stage in the trellis and set the metrics for all states in the first stage to zero.
2. For each state in the next stage, find the “distance” of each branch to it from the next-received subsequence of C′(X) and add it to the metric of the current state from which it branches.
3. Choose the minimum of the values calculated in Step 2 as the metric for the given stage in the next stage, and choose the branch leading to it as the survivor branch to that state.
4. Repeat Steps 2 and 3 until the end of the trellis network is reached.
5. Select the state in the last stage of the trellis network having the minimum metric and work backwards to the beginning by selecting survivor paths to produce the best guess about C(X).
If the coder is known to start from an all-zero state, the system is preferably designed so that traceback is always done to the all-zero state in the first stage. This can be done by, for example, initializing the all-zero state to zero and initializing the other states to large values.
Also, there are various techniques available to determine the state from which to begin a traceback. For example, at the end of a frame when the coder ends in a known state (in the example, 00), start the traceback from that known state.
Application of the Viterbi decoding algorithm to the corrupted stream C′ (and the trellis network of FIG. 2C is shown in FIG. 4. Here,                the metric for a state is shown at its center;        the distance of a current subsequence from a given branch is shown by a number above the branch;        survivor branches (except for those in the best guess path) have a white arrowhead; and        the best guess path is in bold.        
First, metrics of all states in the initial stage are set to zero. Then, the distance (here, the Hamming distance) between the subsequence 11 and each branch value is assigned to that branch. For the first node, the two branches are 00 and 11, so they receive values of 2 and 0. The next node has branches 01 and 10, so each of these branches receives a metric of 1. The third node has branches 11 and 00, so they respectively receive values of 0 and 2. Finally, the fourth node has branches 10 and 01 which each receive a Hamming distance of 1. Then, for the first state in the second stage, the two branch values to it are 2 and 0, so its metric is set at 0 and the 0 branch from the third state in the previous stage is set as its survivor branch. For the second state in the second stage, the two branch values are 0 and 2, so its metric is set at 0 and the 0 branch from the first stage in the first stage is set as its survivor branch. Next, the third stage in the second stage receives values of 1 and 1, so its metric is set to 1 and one side is randomly or deterministically set as the survivor branch. Finally, the last state in the second stage receives values of 1 and 1, so it has a metric of 1 and both branches are set as survivor branches.
This process is repeated to the end of the trellis as shown in FIG. 4. Then, starting at the first node in the last stage (since it has the lowest metric of the last stage), survivor paths are traced back to the first stage. As can be seen from FIG. 4, the result is the same path traveled in the error-free case. Thus, the Viterbi algorithm has successfully eliminated the error contribution of n(t).
Although the Viterbi algorithm works well for situations such as those given above, it is not always practical to directly implement the algorithm in this way. For example, some communication systems make use of alternative information-carrying techniques such as quadrature amplitude modulation (QAM), which requires alternative methods of retrieving the received data stream. Additionally, some communication systems make use of interleaving and other techniques which restricts the type of decoding systems that can be used therein. Thus, there is a need for a decoding technique that addresses these issues.
Also, although the Viterbi algorithm works well for the situations described above, there are improvements that can be made to increase its usefulness. For example, consider the case of an OFDM system with interleaved data mapped to multilevel QAM constellation points. In this case, it is impossible to use Euclidean distance measurements to determine the proper weights to use in the algorithm, since the multiple bits represented by a single measurement are non-sequential in the trellis.
Further, the Viterbi algorithm in its current state does not allow for unequal weighting of bits based on knowledge of their error probability. This unequal error probability may be due to relative position in a multi-level constellation, or position in time, frequency, or space which is more or less likely to be susceptible to noise or interference than other positions.
Also, one of the primary burdens for wireless data transceivers, in terms of both processing latency and consumed integrated circuit real estate, is data decoding such as described above. Available wireless receivers fail to differentiate between reliable (good) and unreliable (bad) bits. Thus, even though bad bits are more difficult to decode and are often discarded once decoded, all bits, both good and bad, are presently utilized equally in available decoding processes. There is therefore a need in the art for a method of analyzing data to determine, in real time, its reliability and utilizing such information before decoding the analyzed data.